/*!
\file AlgFloyd.cpp
\brief Contains implementation of AlgFloyd.
\ingroup Plugins
*/

#include"AlgFloyd.h" 

AlgFloyd::AlgFloyd( Graph *g ): Algorithm( g ){
	for( int i = 0; i < g->numNodes(); i++ ){
		QList<Edge> edges = g->edgesFrom( g->node(i) );
		for( int j = 0; j < edges.size(); j++ ){
			for( int k = j+1; k < edges.size() && j >= 0; k++ ){
				if( g->isDirected() && edges[j].to() == edges[k].to() ){
					if( edges[j].label().toInt() > edges[k].label().toInt() ){
						g->removeEdge(edges[j]);
						edges.takeAt(j);
						j--;
					}else{
						g->removeEdge(edges[k]);
						edges.takeAt(k);
						k--;
					}
				}else if( !g->isDirected() ){
					int removeThis = -1;
					if( edges[j].from() == edges[k].from() && edges[j].to() == edges[k].to() ){
						removeThis = edges[j].label().toInt() > edges[k].label().toInt() ? j : k;
					}else if( edges[j].from() == edges[k].to() && edges[j].to() == edges[k].from() ){
						removeThis = edges[j].label().toInt() > edges[k].label().toInt() ? j : k;
					}
					if( removeThis >= 0 ){
						g->removeEdge(edges[removeThis]);
						edges.takeAt(removeThis);
						if( removeThis == j )
							j--;
						else
							k--;
					}
				}
						
			}
		}
	}
}

AlgFloyd::~AlgFloyd(){
	
}

void AlgFloyd::run(){
	int n = graph()->numNodes();
	for( int k = 0; k < n; k++ ){
		for( int v = 0; v < n; v++ ){
			for( int w = 0; w < n; w++ ){
				const Edge *p;
				int costvk = cost(v,k);
				int costkw = cost(k,w);
				int costvw = cost(v,w, &p);
				
				if( costvk + costkw < costvw ){
					if( costvw < INFINITY )
						graph()->removeEdge( *p );
					
					if( costvk+costkw >= INFINITY )
						continue;
					const Edge &e = graph()->createEdge( graph()->node(v), graph()->node(w), QString().setNum(costvk+costkw) );
					highlight(e);
				}
			}
		}
	}
}

int AlgFloyd::cost( int i, int j, const Edge **e ){
	if( i == j )
		return 0;
	int edgeID = (*graph())[i][j];
	if( edgeID < 0 )
		return INFINITY;
	
	const Edge &edge = graph()->edgeWithId(edgeID);
	if( e != 0 )
		*e = &edge;
		
	return edge.label().toInt();
}
